package com.justnow.solution15;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 参考
     * https://leetcode-cn.com/problems/3sum/solution/pai-xu-shuang-zhi-zhen-zhu-xing-jie-shi-python3-by/
 */
public class Solution15 {

    public static void main(String[] args) {
        Solution15 solution15 = new Solution15();
        int[] nums = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> lists = solution15.threeSum(nums);
        for (List<Integer> list : lists) {
            for (Integer integer : list) {
                System.out.println(integer);
            }
            System.out.println("---------------------------------------");
        }
    }
    public List<List<Integer>> threeSum(int[] nums) {
        if (nums == null || nums.length < 0)
            return null;
        List<List<Integer>> lists = new ArrayList<>();
        int n = nums.length;
        Arrays.sort(nums);
        int left = 0;
        int right = 0;

        for (int i = 0; i < n; i++) {
            //从做到右开始逼近
            if (nums[i] > 0)
                return lists;
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            left = i + 1;
            right = n - 1;
            while(left < right) {
                int temp = nums[i] + nums[left] + nums[right];
                if (temp == 0) {
                    ArrayList<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    lists.add(list);
                    while (left < right && nums[left] == nums[left + 1]) //去重的作用
                        left++;
                    while (left < right && nums[right] == nums[right - 1]) //去重的作用
                        right--;
                    left++;
                    right--;
                } else if (temp > 0) {
                    right--;
                } else {
                    left++;
                }
            }

        }
        return lists;
    }
}
